﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;
using System.Reflection.Emit;
using System.Threading;

namespace System.Linq.Dynamic
{

    public static class DynamicQueryable
    {

        public static IQueryable<T> Where<T>(this IQueryable<T> source, string predicate, params object[] values)
        {

            return (IQueryable<T>)Where((IQueryable)source, predicate, values);

        }



        public static IQueryable Where(this IQueryable source, string predicate, params object[] values)
        {

            if (source == null) throw new ArgumentNullException("source");

            if (predicate == null) throw new ArgumentNullException("predicate");

            LambdaExpression lambda = DynamicExpression.ParseLambda(source.ElementType, typeof(bool), predicate, values);

            return source.Provider.CreateQuery(

                Expression.Call(

                    typeof(Queryable), "Where",

                    new Type[] { source.ElementType },

                    source.Expression, Expression.Quote(lambda)));

        }



        public static IQueryable Select(this IQueryable source, string selector, params object[] values)
        {

            if (source == null) throw new ArgumentNullException("source");

            if (selector == null) throw new ArgumentNullException("selector");

            LambdaExpression lambda = DynamicExpression.ParseLambda(source.ElementType, null, selector, values);

            return source.Provider.CreateQuery(

                Expression.Call(

                    typeof(Queryable), "Select",

                    new Type[] { source.ElementType, lambda.Body.Type },

                    source.Expression, Expression.Quote(lambda)));

        }



        public static IQueryable<T> OrderBy<T>(this IQueryable<T> source, string ordering, params object[] values)
        {

            return (IQueryable<T>)OrderBy((IQueryable)source, ordering, values);

        }



        public static IQueryable OrderBy(this IQueryable source, string ordering, params object[] values)
        {

            if (source == null) throw new ArgumentNullException("source");

            if (ordering == null) throw new ArgumentNullException("ordering");

            ParameterExpression[] parameters = new ParameterExpression[] {

                Expression.Parameter(source.ElementType, "") };

            ExpressionParser parser = new ExpressionParser(parameters, ordering, values);

            IEnumerable<DynamicOrdering> orderings = parser.ParseOrdering();

            Expression queryExpr = source.Expression;

            string methodAsc = "OrderBy";

            string methodDesc = "OrderByDescending";

            foreach (DynamicOrdering o in orderings)
            {

                queryExpr = Expression.Call(

                    typeof(Queryable), o.Ascending ? methodAsc : methodDesc,

                    new Type[] { source.ElementType, o.Selector.Type },

                    queryExpr, Expression.Quote(Expression.Lambda(o.Selector, parameters)));

                methodAsc = "ThenBy";

                methodDesc = "ThenByDescending";

            }

            return source.Provider.CreateQuery(queryExpr);

        }



        public static IQueryable Take(this IQueryable source, int count)
        {

            if (source == null) throw new ArgumentNullException("source");

            return source.Provider.CreateQuery(

                Expression.Call(

                    typeof(Queryable), "Take",

                    new Type[] { source.ElementType },

                    source.Expression, Expression.Constant(count)));

        }



        public static IQueryable Skip(this IQueryable source, int count)
        {

            if (source == null) throw new ArgumentNullException("source");

            return source.Provider.CreateQuery(

                Expression.Call(

                    typeof(Queryable), "Skip",

                    new Type[] { source.ElementType },

                    source.Expression, Expression.Constant(count)));

        }



        public static IQueryable GroupBy(this IQueryable source, string keySelector, string elementSelector, params object[] values)
        {

            if (source == null) throw new ArgumentNullException("source");

            if (keySelector == null) throw new ArgumentNullException("keySelector");

            if (elementSelector == null) throw new ArgumentNullException("elementSelector");

            LambdaExpression keyLambda = DynamicExpression.ParseLambda(source.ElementType, null, keySelector, values);

            LambdaExpression elementLambda = DynamicExpression.ParseLambda(source.ElementType, null, elementSelector, values);

            return source.Provider.CreateQuery(

                Expression.Call(

                    typeof(Queryable), "GroupBy",

                    new Type[] { source.ElementType, keyLambda.Body.Type, elementLambda.Body.Type },

                    source.Expression, Expression.Quote(keyLambda), Expression.Quote(elementLambda)));

        }



        public static bool Any(this IQueryable source)
        {

            if (source == null) throw new ArgumentNullException("source");

            return (bool)source.Provider.Execute(

                Expression.Call(

                    typeof(Queryable), "Any",

                    new Type[] { source.ElementType }, source.Expression));

        }



        public static int Count(this IQueryable source)
        {

            if (source == null) throw new ArgumentNullException("source");

            return (int)source.Provider.Execute(

                Expression.Call(

                    typeof(Queryable), "Count",

                    new Type[] { source.ElementType }, source.Expression));

        }

    }



    public abstract class DynamicClass
    {

        public override string ToString()
        {

            PropertyInfo[] props = this.GetType().GetProperties(BindingFlags.Instance | BindingFlags.Public);

            StringBuilder sb = new StringBuilder();

            sb.Append("{");

            for (int i = 0; i < props.Length; i++)
            {

                if (i > 0) sb.Append(", ");

                sb.Append(props[i].Name);

                sb.Append("=");

                sb.Append(props[i].GetValue(this, null));

            }

            sb.Append("}");

            return sb.ToString();

        }

    }



    public class DynamicProperty
    {

        string name;

        Type type;



        public DynamicProperty(string name, Type type)
        {

            if (name == null) throw new ArgumentNullException("name");

            if (type == null) throw new ArgumentNullException("type");

            this.name = name;

            this.type = type;

        }



        public string Name
        {

            get { return name; }

        }



        public Type Type
        {

            get { return type; }

        }

    }



    public static class DynamicExpression
    {

        public static Expression Parse(Type resultType, string expression, params object[] values)
        {

            ExpressionParser parser = new ExpressionParser(null, expression, values);

            return parser.Parse(resultType);

        }



        public static LambdaExpression ParseLambda(Type itType, Type resultType, string expression, params object[] values)
        {

            return ParseLambda(new ParameterExpression[] { Expression.Parameter(itType, "") }, resultType, expression, values);

        }



        public static LambdaExpression ParseLambda(ParameterExpression[] parameters, Type resultType, string expression, params object[] values)
        {

            ExpressionParser parser = new ExpressionParser(parameters, expression, values);

            return Expression.Lambda(parser.Parse(resultType), parameters);

        }



        public static Expression<Func<T, S>> ParseLambda<T, S>(string expression, params object[] values)
        {

            return (Expression<Func<T, S>>)ParseLambda(typeof(T), typeof(S), expression, values);

        }



        public static Type CreateClass(params DynamicProperty[] properties)
        {

            return ClassFactory.Instance.GetDynamicClass(properties);

        }



        public static Type CreateClass(IEnumerable<DynamicProperty> properties)
        {

            return ClassFactory.Instance.GetDynamicClass(properties);

        }

    }



    internal class DynamicOrdering
    {

        public Expression Selector;

        public bool Ascending;

    }



    internal class Signature : IEquatable<Signature>
    {

        public DynamicProperty[] properties;

        public int hashCode;



        public Signature(IEnumerable<DynamicProperty> properties)
        {

            this.properties = properties.ToArray();

            hashCode = 0;

            foreach (DynamicProperty p in properties)
            {

                hashCode ^= p.Name.GetHashCode() ^ p.Type.GetHashCode();

            }

        }



        public override int GetHashCode()
        {

            return hashCode;

        }



        public override bool Equals(object obj)
        {

            return obj is Signature ? Equals((Signature)obj) : false;

        }



        public bool Equals(Signature other)
        {

            if (properties.Length != other.properties.Length) return false;

            for (int i = 0; i < properties.Length; i++)
            {

                if (properties[i].Name != other.properties[i].Name ||

                    properties[i].Type != other.properties[i].Type) return false;

            }

            return true;

        }

    }



    internal class ClassFactory
    {

        public static readonly ClassFactory Instance = new ClassFactory();



        static ClassFactory() { }  // Trigger lazy initialization of static fields



        ModuleBuilder module;

        Dictionary<Signature, Type> classes;

        int classCount;

        ReaderWriterLock rwLock;



        private ClassFactory()
        {

            AssemblyName name = new AssemblyName("DynamicClasses");

            AssemblyBuilder assembly = AppDomain.CurrentDomain.DefineDynamicAssembly(name, AssemblyBuilderAccess.Run);

#if ENABLE_LINQ_PARTIAL_TRUST

            new ReflectionPermission(PermissionState.Unrestricted).Assert();

#endif

            try
            {

                module = assembly.DefineDynamicModule("Module");

            }

            finally
            {

#if ENABLE_LINQ_PARTIAL_TRUST

                PermissionSet.RevertAssert();

#endif

            }

            classes = new Dictionary<Signature, Type>();

            rwLock = new ReaderWriterLock();

        }



        public Type GetDynamicClass(IEnumerable<DynamicProperty> properties)
        {

            rwLock.AcquireReaderLock(Timeout.Infinite);

            try
            {

                Signature signature = new Signature(properties);

                Type type;

                if (!classes.TryGetValue(signature, out type))
                {

                    type = CreateDynamicClass(signature.properties);

                    classes.Add(signature, type);

                }

                return type;

            }

            finally
            {

                rwLock.ReleaseReaderLock();

            }

        }



        Type CreateDynamicClass(DynamicProperty[] properties)
        {

            LockCookie cookie = rwLock.UpgradeToWriterLock(Timeout.Infinite);

            try
            {

                string typeName = "DynamicClass" + (classCount + 1);

#if ENABLE_LINQ_PARTIAL_TRUST

                new ReflectionPermission(PermissionState.Unrestricted).Assert();

#endif

                try
                {

                    TypeBuilder tb = this.module.DefineType(typeName, TypeAttributes.Class |

                        TypeAttributes.Public, typeof(DynamicClass));

                    FieldInfo[] fields = GenerateProperties(tb, properties);

                    GenerateEquals(tb, fields);

                    GenerateGetHashCode(tb, fields);

                    Type result = tb.CreateType();

                    classCount++;

                    return result;

                }

                finally
                {

#if ENABLE_LINQ_PARTIAL_TRUST

                    PermissionSet.RevertAssert();

#endif

                }

            }

            finally
            {

                rwLock.DowngradeFromWriterLock(ref cookie);

            }

        }



        FieldInfo[] GenerateProperties(TypeBuilder tb, DynamicProperty[] properties)
        {

            FieldInfo[] fields = new FieldBuilder[properties.Length];

            for (int i = 0; i < properties.Length; i++)
            {

                DynamicProperty dp = properties[i];

                FieldBuilder fb = tb.DefineField("_" + dp.Name, dp.Type, FieldAttributes.Private);

                PropertyBuilder pb = tb.DefineProperty(dp.Name, PropertyAttributes.HasDefault, dp.Type, null);

                MethodBuilder mbGet = tb.DefineMethod("get_" + dp.Name,

                    MethodAttributes.Public | MethodAttributes.SpecialName | MethodAttributes.HideBySig,

                    dp.Type, Type.EmptyTypes);

                ILGenerator genGet = mbGet.GetILGenerator();

                genGet.Emit(OpCodes.Ldarg_0);

                genGet.Emit(OpCodes.Ldfld, fb);

                genGet.Emit(OpCodes.Ret);

                MethodBuilder mbSet = tb.DefineMethod("set_" + dp.Name,

                    MethodAttributes.Public | MethodAttributes.SpecialName | MethodAttributes.HideBySig,

                    null, new Type[] { dp.Type });

                ILGenerator genSet = mbSet.GetILGenerator();

                genSet.Emit(OpCodes.Ldarg_0);

                genSet.Emit(OpCodes.Ldarg_1);

                genSet.Emit(OpCodes.Stfld, fb);

                genSet.Emit(OpCodes.Ret);

                pb.SetGetMethod(mbGet);

                pb.SetSetMethod(mbSet);

                fields[i] = fb;

            }

            return fields;

        }



        void GenerateEquals(TypeBuilder tb, FieldInfo[] fields)
        {

            MethodBuilder mb = tb.DefineMethod("Equals",

                MethodAttributes.Public | MethodAttributes.ReuseSlot |

                MethodAttributes.Virtual | MethodAttributes.HideBySig,

                typeof(bool), new Type[] { typeof(object) });

            ILGenerator gen = mb.GetILGenerator();

            LocalBuilder other = gen.DeclareLocal(tb);

            Label next = gen.DefineLabel();

            gen.Emit(OpCodes.Ldarg_1);

            gen.Emit(OpCodes.Isinst, tb);

            gen.Emit(OpCodes.Stloc, other);

            gen.Emit(OpCodes.Ldloc, other);

            gen.Emit(OpCodes.Brtrue_S, next);

            gen.Emit(OpCodes.Ldc_I4_0);

            gen.Emit(OpCodes.Ret);

            gen.MarkLabel(next);

            foreach (FieldInfo field in fields)
            {

                Type ft = field.FieldType;

                Type ct = typeof(EqualityComparer<>).MakeGenericType(ft);

                next = gen.DefineLabel();

                gen.EmitCall(OpCodes.Call, ct.GetMethod("get_Default"), null);

                gen.Emit(OpCodes.Ldarg_0);

                gen.Emit(OpCodes.Ldfld, field);

                gen.Emit(OpCodes.Ldloc, other);

                gen.Emit(OpCodes.Ldfld, field);

                gen.EmitCall(OpCodes.Callvirt, ct.GetMethod("Equals", new Type[] { ft, ft }), null);

                gen.Emit(OpCodes.Brtrue_S, next);

                gen.Emit(OpCodes.Ldc_I4_0);

                gen.Emit(OpCodes.Ret);

                gen.MarkLabel(next);

            }

            gen.Emit(OpCodes.Ldc_I4_1);

            gen.Emit(OpCodes.Ret);

        }



        void GenerateGetHashCode(TypeBuilder tb, FieldInfo[] fields)
        {

            MethodBuilder mb = tb.DefineMethod("GetHashCode",

                MethodAttributes.Public | MethodAttributes.ReuseSlot |

                MethodAttributes.Virtual | MethodAttributes.HideBySig,

                typeof(int), Type.EmptyTypes);

            ILGenerator gen = mb.GetILGenerator();

            gen.Emit(OpCodes.Ldc_I4_0);

            foreach (FieldInfo field in fields)
            {

                Type ft = field.FieldType;

                Type ct = typeof(EqualityComparer<>).MakeGenericType(ft);

                gen.EmitCall(OpCodes.Call, ct.GetMethod("get_Default"), null);

                gen.Emit(OpCodes.Ldarg_0);

                gen.Emit(OpCodes.Ldfld, field);

                gen.EmitCall(OpCodes.Callvirt, ct.GetMethod("GetHashCode", new Type[] { ft }), null);

                gen.Emit(OpCodes.Xor);

            }

            gen.Emit(OpCodes.Ret);

        }

    }



    public sealed class ParseException : Exception
    {

        int position;



        public ParseException(string message, int position)

            : base(message)
        {

            this.position = position;

        }



        public int Position
        {

            get { return position; }

        }



        public override string ToString()
        {

            return string.Format(Res.ParseExceptionFormat, Message, position);

        }

    }



    internal class ExpressionParser
    {

        struct Token
        {

            public TokenId id;

            public string text;

            public int pos;

        }



        enum TokenId
        {

            Unknown,

            End,

            Identifier,

            StringLiteral,

            IntegerLiteral,

            RealLiteral,

            Exclamation,

            Percent,

            Amphersand,

            OpenParen,

            CloseParen,

            Asterisk,

            Plus,

            Comma,

            Minus,

            Dot,

            Slash,

            Colon,

            LessThan,

            Equal,

            GreaterThan,

            Question,

            OpenBracket,

            CloseBracket,

            Bar,

            ExclamationEqual,

            DoubleAmphersand,

            LessThanEqual,

            LessGreater,

            DoubleEqual,

            GreaterThanEqual,

            DoubleBar

        }



        interface ILogicalSignatures
        {

            void F(bool x, bool y);

            void F(bool? x, bool? y);

        }



        interface IArithmeticSignatures
        {

            void F(int x, int y);

            void F(uint x, uint y);

            void F(long x, long y);

            void F(ulong x, ulong y);

            void F(float x, float y);

            void F(double x, double y);

            void F(decimal x, decimal y);

            void F(int? x, int? y);

            void F(uint? x, uint? y);

            void F(long? x, long? y);

            void F(ulong? x, ulong? y);

            void F(float? x, float? y);

            void F(double? x, double? y);

            void F(decimal? x, decimal? y);

        }



        interface IRelationalSignatures : IArithmeticSignatures
        {

            void F(string x, string y);

            void F(char x, char y);

            void F(DateTime x, DateTime y);

            void F(TimeSpan x, TimeSpan y);

            void F(char? x, char? y);

            void F(DateTime? x, DateTime? y);

            void F(TimeSpan? x, TimeSpan? y);

        }



        interface IEqualitySignatures : IRelationalSignatures
        {

            void F(bool x, bool y);

            void F(bool? x, bool? y);

        }



        interface IAddSignatures : IArithmeticSignatures
        {

            void F(DateTime x, TimeSpan y);

            void F(TimeSpan x, TimeSpan y);

            void F(DateTime? x, TimeSpan? y);

            void F(TimeSpan? x, TimeSpan? y);

        }



        interface ISubtractSignatures : IAddSignatures
        {

            void F(DateTime x, DateTime y);

            void F(DateTime? x, DateTime? y);

        }



        interface INegationSignatures
        {

            void F(int x);

            void F(long x);

            void F(float x);

            void F(double x);

            void F(decimal x);

            void F(int? x);

            void F(long? x);

            void F(float? x);

            void F(double? x);

            void F(decimal? x);

        }



        interface INotSignatures
        {

            void F(bool x);

            void F(bool? x);

        }



        interface IEnumerableSignatures
        {

            void Where(bool predicate);

            void Any();

            void Any(bool predicate);

            void All(bool predicate);

            void Count();

            void Count(bool predicate);

            void Min(object selector);

            void Max(object selector);

            void Sum(int selector);

            void Sum(int? selector);

            void Sum(long selector);

            void Sum(long? selector);

            void Sum(float selector);

            void Sum(float? selector);

            void Sum(double selector);

            void Sum(double? selector);

            void Sum(decimal selector);

            void Sum(decimal? selector);

            void Average(int selector);

            void Average(int? selector);

            void Average(long selector);

            void Average(long? selector);

            void Average(float selector);

            void Average(float? selector);

            void Average(double selector);

            void Average(double? selector);

            void Average(decimal selector);

            void Average(decimal? selector);

        }



        static readonly Type[] predefinedTypes = {

            typeof(Object),

            typeof(Boolean),

            typeof(Char),

            typeof(String),

            typeof(SByte),

            typeof(Byte),

            typeof(Int16),

            typeof(UInt16),

            typeof(Int32),

            typeof(UInt32),

            typeof(Int64),

            typeof(UInt64),

            typeof(Single),

            typeof(Double),

            typeof(Decimal),

            typeof(DateTime),

            typeof(TimeSpan),

            typeof(Guid),

            typeof(Math),

            typeof(Convert)

        };



        static readonly Expression trueLiteral = Expression.Constant(true);

        static readonly Expression falseLiteral = Expression.Constant(false);

        static readonly Expression nullLiteral = Expression.Constant(null);



        static readonly string keywordIt = "it";

        static readonly string keywordIif = "iif";

        static readonly string keywordNew = "new";



        static Dictionary<string, object> keywords;



        Dictionary<string, object> symbols;

        IDictionary<string, object> externals;

        Dictionary<Expression, string> literals;

        ParameterExpression it;

        string text;

        int textPos;

        int textLen;

        char ch;

        Token token;



        public ExpressionParser(ParameterExpression[] parameters, string expression, object[] values)
        {

            if (expression == null) throw new ArgumentNullException("expression");

            if (keywords == null) keywords = CreateKeywords();

            symbols = new Dictionary<string, object>(StringComparer.OrdinalIgnoreCase);

            literals = new Dictionary<Expression, string>();

            if (parameters != null) ProcessParameters(parameters);

            if (values != null) ProcessValues(values);

            text = expression;

            textLen = text.Length;

            SetTextPos(0);

            NextToken();

        }



        void ProcessParameters(ParameterExpression[] parameters)
        {

            foreach (ParameterExpression pe in parameters)

                if (!String.IsNullOrEmpty(pe.Name))

                    AddSymbol(pe.Name, pe);

            if (parameters.Length == 1 && String.IsNullOrEmpty(parameters[0].Name))

                it = parameters[0];

        }



        void ProcessValues(object[] values)
        {

            for (int i = 0; i < values.Length; i++)
            {

                object value = values[i];

                if (i == values.Length - 1 && value is IDictionary<string, object>)
                {

                    externals = (IDictionary<string, object>)value;

                }

                else
                {

                    AddSymbol("@" + i.ToString(System.Globalization.CultureInfo.InvariantCulture), value);

                }

            }

        }



        void AddSymbol(string name, object value)
        {

            if (symbols.ContainsKey(name))

                throw ParseError(Res.DuplicateIdentifier, name);

            symbols.Add(name, value);

        }



        public Expression Parse(Type resultType)
        {

            int exprPos = token.pos;

            Expression expr = ParseExpression();

            if (resultType != null)

                if ((expr = PromoteExpression(expr, resultType, true)) == null)

                    throw ParseError(exprPos, Res.ExpressionTypeMismatch, GetTypeName(resultType));

            ValidateToken(TokenId.End, Res.SyntaxError);

            return expr;

        }



#pragma warning disable 0219

        public IEnumerable<DynamicOrdering> ParseOrdering()
        {

            List<DynamicOrdering> orderings = new List<DynamicOrdering>();

            while (true)
            {

                Expression expr = ParseExpression();

                bool ascending = true;

                if (TokenIdentifierIs("asc") || TokenIdentifierIs("ascending"))
                {

                    NextToken();

                }

                else if (TokenIdentifierIs("desc") || TokenIdentifierIs("descending"))
                {

                    NextToken();

                    ascending = false;

                }

                orderings.Add(new DynamicOrdering { Selector = expr, Ascending = ascending });

                if (token.id != TokenId.Comma) break;

                NextToken();

            }

            ValidateToken(TokenId.End, Res.SyntaxError);

            return orderings;

        }

#pragma warning restore 0219



        // ?: operator

        Expression ParseExpression()
        {

            int errorPos = token.pos;

            Expression expr = ParseLogicalOr();

            if (token.id == TokenId.Question)
            {

                NextToken();

                Expression expr1 = ParseExpression();

                ValidateToken(TokenId.Colon, Res.ColonExpected);

                NextToken();

                Expression expr2 = ParseExpression();

                expr = GenerateConditional(expr, expr1, expr2, errorPos);

            }

            return expr;

        }



        // ||, or operator

        Expression ParseLogicalOr()
        {

            Expression left = ParseLogicalAnd();

            while (token.id == TokenId.DoubleBar || TokenIdentifierIs("or"))
            {

                Token op = token;

                NextToken();

                Expression right = ParseLogicalAnd();

                CheckAndPromoteOperands(typeof(ILogicalSignatures), op.text, ref left, ref right, op.pos);

                left = Expression.OrElse(left, right);

            }

            return left;

        }



        // &&, and operator

        Expression ParseLogicalAnd()
        {

            Expression left = ParseComparison();

            while (token.id == TokenId.DoubleAmphersand || TokenIdentifierIs("and"))
            {

                Token op = token;

                NextToken();

                Expression right = ParseComparison();

                CheckAndPromoteOperands(typeof(ILogicalSignatures), op.text, ref left, ref right, op.pos);

                left = Expression.AndAlso(left, right);

            }

            return left;

        }



        // =, ==, !=, <>, >, >=, <, <= operators

        Expression ParseComparison()
        {

            Expression left = ParseAdditive();

            while (token.id == TokenId.Equal || token.id == TokenId.DoubleEqual ||

                token.id == TokenId.ExclamationEqual || token.id == TokenId.LessGreater ||

                token.id == TokenId.GreaterThan || token.id == TokenId.GreaterThanEqual ||

                token.id == TokenId.LessThan || token.id == TokenId.LessThanEqual)
            {

                Token op = token;

                NextToken();

                Expression right = ParseAdditive();

                bool isEquality = op.id == TokenId.Equal || op.id == TokenId.DoubleEqual ||

                    op.id == TokenId.ExclamationEqual || op.id == TokenId.LessGreater;

                if (isEquality && ((!left.Type.IsValueType && !right.Type.IsValueType) || ((left.Type == typeof(Guid) || left.Type == typeof(Guid?)) && (right.Type == typeof(Guid) || right.Type == typeof(Guid?))))) 
                {
                    if (left.Type != right.Type)
                    {

                        if (left.Type.IsAssignableFrom(right.Type))
                        {

                            right = Expression.Convert(right, left.Type);

                        }

                        else if (right.Type.IsAssignableFrom(left.Type))
                        {

                            left = Expression.Convert(left, right.Type);

                        }

                        else
                        {

                            throw IncompatibleOperandsError(op.text, left, right, op.pos);

                        }

                    }

                }

                else if (IsEnumType(left.Type) || IsEnumType(right.Type))
                {

                    if (left.Type != right.Type)
                    {

                        Expression e;

                        if ((e = PromoteExpression(right, left.Type, true)) != null)
                        {

                            right = e;

                        }

                        else if ((e = PromoteExpression(left, right.Type, true)) != null)
                        {

                            left = e;

                        }

                        else
                        {

                            throw IncompatibleOperandsError(op.text, left, right, op.pos);

                        }

                    }

                }

                else
                {

                    CheckAndPromoteOperands(isEquality ? typeof(IEqualitySignatures) : typeof(IRelationalSignatures),

                        op.text, ref left, ref right, op.pos);

                }

                switch (op.id)
                {

                    case TokenId.Equal:

                    case TokenId.DoubleEqual:

                        left = GenerateEqual(left, right);

                        break;

                    case TokenId.ExclamationEqual:

                    case TokenId.LessGreater:

                        left = GenerateNotEqual(left, right);

                        break;

                    case TokenId.GreaterThan:

                        left = GenerateGreaterThan(left, right);

                        break;

                    case TokenId.GreaterThanEqual:

                        left = GenerateGreaterThanEqual(left, right);

                        break;

                    case TokenId.LessThan:

                        left = GenerateLessThan(left, right);

                        break;

                    case TokenId.LessThanEqual:

                        left = GenerateLessThanEqual(left, right);

                        break;

                }

            }

            return left;

        }



        // +, -, & operators

        Expression ParseAdditive()
        {

            Expression left = ParseMultiplicative();

            while (token.id == TokenId.Plus || token.id == TokenId.Minus ||

                token.id == TokenId.Amphersand)
            {

                Token op = token;

                NextToken();

                Expression right = ParseMultiplicative();

                switch (op.id)
                {

                    case TokenId.Plus:

                        if (left.Type == typeof(string) || right.Type == typeof(string))

                            goto case TokenId.Amphersand;

                        CheckAndPromoteOperands(typeof(IAddSignatures), op.text, ref left, ref right, op.pos);

                        left = GenerateAdd(left, right);

                        break;

                    case TokenId.Minus:

                        CheckAndPromoteOperands(typeof(ISubtractSignatures), op.text, ref left, ref right, op.pos);

                        left = GenerateSubtract(left, right);

                        break;

                    case TokenId.Amphersand:

                        left = GenerateStringConcat(left, right);

                        break;

                }

            }

            return left;

        }



        // *, /, %, mod operators

        Expression ParseMultiplicative()
        {

            Expression left = ParseUnary();

            while (token.id == TokenId.Asterisk || token.id == TokenId.Slash ||

                token.id == TokenId.Percent || TokenIdentifierIs("mod"))
            {

                Token op = token;

                NextToken();

                Expression right = ParseUnary();

                CheckAndPromoteOperands(typeof(IArithmeticSignatures), op.text, ref left, ref right, op.pos);

                switch (op.id)
                {

                    case TokenId.Asterisk:

                        left = Expression.Multiply(left, right);

                        break;

                    case TokenId.Slash:

                        left = Expression.Divide(left, right);

                        break;

                    case TokenId.Percent:

                    case TokenId.Identifier:

                        left = Expression.Modulo(left, right);

                        break;

                }

            }

            return left;

        }



        // -, !, not unary operators

        Expression ParseUnary()
        {

            if (token.id == TokenId.Minus || token.id == TokenId.Exclamation ||

                TokenIdentifierIs("not"))
            {

                Token op = token;

                NextToken();

                if (op.id == TokenId.Minus && (token.id == TokenId.IntegerLiteral ||

                    token.id == TokenId.RealLiteral))
                {

                    token.text = "-" + token.text;

                    token.pos = op.pos;

                    return ParsePrimary();

                }

                Expression expr = ParseUnary();

                if (op.id == TokenId.Minus)
                {

                    CheckAndPromoteOperand(typeof(INegationSignatures), op.text, ref expr, op.pos);

                    expr = Expression.Negate(expr);

                }

                else
                {

                    CheckAndPromoteOperand(typeof(INotSignatures), op.text, ref expr, op.pos);

                    expr = Expression.Not(expr);

                }

                return expr;

            }

            return ParsePrimary();

        }



        Expression ParsePrimary()
        {

            Expression expr = ParsePrimaryStart();

            while (true)
            {

                if (token.id == TokenId.Dot)
                {

                    NextToken();

                    expr = ParseMemberAccess(null, expr);

                }

                else if (token.id == TokenId.OpenBracket)
                {

                    expr = ParseElementAccess(expr);

                }

                else
                {

                    break;

                }

            }

            return expr;

        }



        Expression ParsePrimaryStart()
        {

            switch (token.id)
            {

                case TokenId.Identifier:

                    return ParseIdentifier();

                case TokenId.StringLiteral:

                    return ParseStringLiteral();

                case TokenId.IntegerLiteral:

                    return ParseIntegerLiteral();

                case TokenId.RealLiteral:

                    return ParseRealLiteral();

                case TokenId.OpenParen:

                    return ParseParenExpression();

                default:

                    throw ParseError(Res.ExpressionExpected);

            }

        }



        Expression ParseStringLiteral()
        {

            ValidateToken(TokenId.StringLiteral);

            char quote = token.text[0];

            string s = token.text.Substring(1, token.text.Length - 2);

            int start = 0;

            while (true)
            {

                int i = s.IndexOf(quote, start);

                if (i < 0) break;

                s = s.Remove(i, 1);

                start = i + 1;

            }

            if (quote == '\'')
            {

                if (s.Length != 1)

                    throw ParseError(Res.InvalidCharacterLiteral);

                NextToken();

                return CreateLiteral(s[0], s);

            }

            NextToken();

            return CreateLiteral(s, s);

        }



        Expression ParseIntegerLiteral()
        {

            ValidateToken(TokenId.IntegerLiteral);

            string text = token.text;

            if (text[0] != '-')
            {

                ulong value;

                if (!UInt64.TryParse(text, out value))

                    throw ParseError(Res.InvalidIntegerLiteral, text);

                NextToken();

                if (value <= (ulong)Int32.MaxValue) return CreateLiteral((int)value, text);

                if (value <= (ulong)UInt32.MaxValue) return CreateLiteral((uint)value, text);

                if (value <= (ulong)Int64.MaxValue) return CreateLiteral((long)value, text);

                return CreateLiteral(value, text);

            }

            else
            {

                long value;

                if (!Int64.TryParse(text, out value))

                    throw ParseError(Res.InvalidIntegerLiteral, text);

                NextToken();

                if (value >= Int32.MinValue && value <= Int32.MaxValue)

                    return CreateLiteral((int)value, text);

                return CreateLiteral(value, text);

            }

        }



        Expression ParseRealLiteral()
        {

            ValidateToken(TokenId.RealLiteral);

            string text = token.text;

            object value = null;

            char last = text[text.Length - 1];

            if (last == 'F' || last == 'f')
            {

                float f;

                if (Single.TryParse(text.Substring(0, text.Length - 1), out f)) value = f;

            }

            else
            {

                double d;

                if (Double.TryParse(text, out d)) value = d;

            }

            if (value == null) throw ParseError(Res.InvalidRealLiteral, text);

            NextToken();

            return CreateLiteral(value, text);

        }



        Expression CreateLiteral(object value, string text)
        {

            ConstantExpression expr = Expression.Constant(value);

            literals.Add(expr, text);

            return expr;

        }



        Expression ParseParenExpression()
        {

            ValidateToken(TokenId.OpenParen, Res.OpenParenExpected);

            NextToken();

            Expression e = ParseExpression();

            ValidateToken(TokenId.CloseParen, Res.CloseParenOrOperatorExpected);

            NextToken();

            return e;

        }



        Expression ParseIdentifier()
        {

            ValidateToken(TokenId.Identifier);

            object value;

            if (keywords.TryGetValue(token.text, out value))
            {

                if (value is Type) return ParseTypeAccess((Type)value);

                if (value == (object)keywordIt) return ParseIt();

                if (value == (object)keywordIif) return ParseIif();

                if (value == (object)keywordNew) return ParseNew();

                NextToken();

                return (Expression)value;

            }

            if (symbols.TryGetValue(token.text, out value) ||

                externals != null && externals.TryGetValue(token.text, out value))
            {

                Expression expr = value as Expression;

                if (expr == null)
                {

                    expr = Expression.Constant(value);

                }

                else
                {

                    LambdaExpression lambda = expr as LambdaExpression;

                    if (lambda != null) return ParseLambdaInvocation(lambda);

                }

                NextToken();

                return expr;

            }

            if (it != null) return ParseMemberAccess(null, it);

            throw ParseError(Res.UnknownIdentifier, token.text);

        }



        Expression ParseIt()
        {

            if (it == null)

                throw ParseError(Res.NoItInScope);

            NextToken();

            return it;

        }



        Expression ParseIif()
        {

            int errorPos = token.pos;

            NextToken();

            Expression[] args = ParseArgumentList();

            if (args.Length != 3)

                throw ParseError(errorPos, Res.IifRequiresThreeArgs);

            return GenerateConditional(args[0], args[1], args[2], errorPos);

        }



        Expression GenerateConditional(Expression test, Expression expr1, Expression expr2, int errorPos)
        {

            if (test.Type != typeof(bool))

                throw ParseError(errorPos, Res.FirstExprMustBeBool);

            if (expr1.Type != expr2.Type)
            {

                Expression expr1as2 = expr2 != nullLiteral ? PromoteExpression(expr1, expr2.Type, true) : null;

                Expression expr2as1 = expr1 != nullLiteral ? PromoteExpression(expr2, expr1.Type, true) : null;

                if (expr1as2 != null && expr2as1 == null)
                {

                    expr1 = expr1as2;

                }

                else if (expr2as1 != null && expr1as2 == null)
                {

                    expr2 = expr2as1;

                }

                else
                {

                    string type1 = expr1 != nullLiteral ? expr1.Type.Name : "null";

                    string type2 = expr2 != nullLiteral ? expr2.Type.Name : "null";

                    if (expr1as2 != null && expr2as1 != null)

                        throw ParseError(errorPos, Res.BothTypesConvertToOther, type1, type2);

                    throw ParseError(errorPos, Res.NeitherTypeConvertsToOther, type1, type2);

                }

            }

            return Expression.Condition(test, expr1, expr2);

        }



        Expression ParseNew()
        {

            NextToken();

            ValidateToken(TokenId.OpenParen, Res.OpenParenExpected);

            NextToken();

            List<DynamicProperty> properties = new List<DynamicProperty>();

            List<Expression> expressions = new List<Expression>();

            while (true)
            {

                int exprPos = token.pos;

                Expression expr = ParseExpression();

                string propName;

                if (TokenIdentifierIs("as"))
                {

                    NextToken();

                    propName = GetIdentifier();

                    NextToken();

                }

                else
                {

                    MemberExpression me = expr as MemberExpression;

                    if (me == null) throw ParseError(exprPos, Res.MissingAsClause);

                    propName = me.Member.Name;

                }

                expressions.Add(expr);

                properties.Add(new DynamicProperty(propName, expr.Type));

                if (token.id != TokenId.Comma) break;

                NextToken();

            }

            ValidateToken(TokenId.CloseParen, Res.CloseParenOrCommaExpected);

            NextToken();

            Type type = DynamicExpression.CreateClass(properties);

            MemberBinding[] bindings = new MemberBinding[properties.Count];

            for (int i = 0; i < bindings.Length; i++)

                bindings[i] = Expression.Bind(type.GetProperty(properties[i].Name), expressions[i]);

            return Expression.MemberInit(Expression.New(type), bindings);

        }



        Expression ParseLambdaInvocation(LambdaExpression lambda)
        {

            int errorPos = token.pos;

            NextToken();

            Expression[] args = ParseArgumentList();

            MethodBase method;

            if (FindMethod(lambda.Type, "Invoke", false, args, out method) != 1)

                throw ParseError(errorPos, Res.ArgsIncompatibleWithLambda);

            return Expression.Invoke(lambda, args);

        }



        Expression ParseTypeAccess(Type type)
        {

            int errorPos = token.pos;

            NextToken();

            if (token.id == TokenId.Question)
            {

                if (!type.IsValueType || IsNullableType(type))

                    throw ParseError(errorPos, Res.TypeHasNoNullableForm, GetTypeName(type));

                type = typeof(Nullable<>).MakeGenericType(type);

                NextToken();

            }

            if (token.id == TokenId.OpenParen)
            {

                Expression[] args = ParseArgumentList();

                MethodBase method;

                switch (FindBestMethod(type.GetConstructors(), args, out method))
                {

                    case 0:

                        if (args.Length == 1)

                            return GenerateConversion(args[0], type, errorPos);

                        throw ParseError(errorPos, Res.NoMatchingConstructor, GetTypeName(type));

                    case 1:

                        return Expression.New((ConstructorInfo)method, args);

                    default:

                        throw ParseError(errorPos, Res.AmbiguousConstructorInvocation, GetTypeName(type));

                }

            }

            ValidateToken(TokenId.Dot, Res.DotOrOpenParenExpected);

            NextToken();

            return ParseMemberAccess(type, null);

        }



        Expression GenerateConversion(Expression expr, Type type, int errorPos)
        {

            Type exprType = expr.Type;

            if (exprType == type) return expr;

            if (exprType.IsValueType && type.IsValueType)
            {

                if ((IsNullableType(exprType) || IsNullableType(type)) &&

                    GetNonNullableType(exprType) == GetNonNullableType(type))

                    return Expression.Convert(expr, type);

                if ((IsNumericType(exprType) || IsEnumType(exprType)) &&

                    (IsNumericType(type)) || IsEnumType(type))

                    return Expression.ConvertChecked(expr, type);

            }

            if (exprType.IsAssignableFrom(type) || type.IsAssignableFrom(exprType) ||

                exprType.IsInterface || type.IsInterface)

                return Expression.Convert(expr, type);

            throw ParseError(errorPos, Res.CannotConvertValue,

                GetTypeName(exprType), GetTypeName(type));

        }



        Expression ParseMemberAccess(Type type, Expression instance)
        {

            if (instance != null) type = instance.Type;

            int errorPos = token.pos;

            string id = GetIdentifier();

            NextToken();

            if (token.id == TokenId.OpenParen)
            {

                if (instance != null && type != typeof(string))
                {

                    Type enumerableType = FindGenericType(typeof(IEnumerable<>), type);

                    if (enumerableType != null)
                    {

                        Type elementType = enumerableType.GetGenericArguments()[0];

                        return ParseAggregate(instance, elementType, id, errorPos);

                    }

                }

                Expression[] args = ParseArgumentList();

                MethodBase mb;

                switch (FindMethod(type, id, instance == null, args, out mb))
                {

                    case 0:

                        throw ParseError(errorPos, Res.NoApplicableMethod,

                            id, GetTypeName(type));

                    case 1:

                        MethodInfo method = (MethodInfo)mb;

                        if (!IsPredefinedType(method.DeclaringType))

                            throw ParseError(errorPos, Res.MethodsAreInaccessible, GetTypeName(method.DeclaringType));

                        if (method.ReturnType == typeof(void))

                            throw ParseError(errorPos, Res.MethodIsVoid,

                                id, GetTypeName(method.DeclaringType));

                        return Expression.Call(instance, (MethodInfo)method, args);

                    default:

                        throw ParseError(errorPos, Res.AmbiguousMethodInvocation,

                            id, GetTypeName(type));

                }

            }

            else
            {

                MemberInfo member = FindPropertyOrField(type, id, instance == null);

                if (member == null)

                    throw ParseError(errorPos, Res.UnknownPropertyOrField,

                        id, GetTypeName(type));

                return member is PropertyInfo ?

                    Expression.Property(instance, (PropertyInfo)member) :

                    Expression.Field(instance, (FieldInfo)member);

            }

        }



        static Type FindGenericType(Type generic, Type type)
        {

            while (type != null && type != typeof(object))
            {

                if (type.IsGenericType && type.GetGenericTypeDefinition() == generic) return type;

                if (generic.IsInterface)
                {

                    foreach (Type intfType in type.GetInterfaces())
                    {

                        Type found = FindGenericType(generic, intfType);

                        if (found != null) return found;

                    }

                }

                type = type.BaseType;

            }

            return null;

        }



        Expression ParseAggregate(Expression instance, Type elementType, string methodName, int errorPos)
        {

            ParameterExpression outerIt = it;

            ParameterExpression innerIt = Expression.Parameter(elementType, "");

            it = innerIt;

            Expression[] args = ParseArgumentList();

            it = outerIt;

            MethodBase signature;

            if (FindMethod(typeof(IEnumerableSignatures), methodName, false, args, out signature) != 1)

                throw ParseError(errorPos, Res.NoApplicableAggregate, methodName);

            Type[] typeArgs;

            if (signature.Name == "Min" || signature.Name == "Max")
            {

                typeArgs = new Type[] { elementType, args[0].Type };

            }

            else
            {

                typeArgs = new Type[] { elementType };

            }

            if (args.Length == 0)
            {

                args = new Expression[] { instance };

            }

            else
            {

                args = new Expression[] { instance, Expression.Lambda(args[0], innerIt) };

            }

            return Expression.Call(typeof(Enumerable), signature.Name, typeArgs, args);

        }



        Expression[] ParseArgumentList()
        {

            ValidateToken(TokenId.OpenParen, Res.OpenParenExpected);

            NextToken();

            Expression[] args = token.id != TokenId.CloseParen ? ParseArguments() : new Expression[0];

            ValidateToken(TokenId.CloseParen, Res.CloseParenOrCommaExpected);

            NextToken();

            return args;

        }



        Expression[] ParseArguments()
        {

            List<Expression> argList = new List<Expression>();

            while (true)
            {

                argList.Add(ParseExpression());

                if (token.id != TokenId.Comma) break;

                NextToken();

            }

            return argList.ToArray();

        }



        Expression ParseElementAccess(Expression expr)
        {

            int errorPos = token.pos;

            ValidateToken(TokenId.OpenBracket, Res.OpenParenExpected);

            NextToken();

            Expression[] args = ParseArguments();

            ValidateToken(TokenId.CloseBracket, Res.CloseBracketOrCommaExpected);

            NextToken();

            if (expr.Type.IsArray)
            {

                if (expr.Type.GetArrayRank() != 1 || args.Length != 1)

                    throw ParseError(errorPos, Res.CannotIndexMultiDimArray);

                Expression index = PromoteExpression(args[0], typeof(int), true);

                if (index == null)

                    throw ParseError(errorPos, Res.InvalidIndex);

                return Expression.ArrayIndex(expr, index);

            }

            else
            {

                MethodBase mb;

                switch (FindIndexer(expr.Type, args, out mb))
                {

                    case 0:

                        throw ParseError(errorPos, Res.NoApplicableIndexer,

                            GetTypeName(expr.Type));

                    case 1:

                        return Expression.Call(expr, (MethodInfo)mb, args);

                    default:

                        throw ParseError(errorPos, Res.AmbiguousIndexerInvocation,

                            GetTypeName(expr.Type));

                }

            }

        }



        static bool IsPredefinedType(Type type)
        {

            foreach (Type t in predefinedTypes) if (t == type) return true;

            return false;

        }



        static bool IsNullableType(Type type)
        {

            return type.IsGenericType && type.GetGenericTypeDefinition() == typeof(Nullable<>);

        }



        static Type GetNonNullableType(Type type)
        {

            return IsNullableType(type) ? type.GetGenericArguments()[0] : type;

        }



        static string GetTypeName(Type type)
        {

            Type baseType = GetNonNullableType(type);

            string s = baseType.Name;

            if (type != baseType) s += '?';

            return s;

        }



        static bool IsNumericType(Type type)
        {

            return GetNumericTypeKind(type) != 0;

        }



        static bool IsSignedIntegralType(Type type)
        {

            return GetNumericTypeKind(type) == 2;

        }



        static bool IsUnsignedIntegralType(Type type)
        {

            return GetNumericTypeKind(type) == 3;

        }



        static int GetNumericTypeKind(Type type)
        {

            type = GetNonNullableType(type);

            if (type.IsEnum) return 0;

            switch (Type.GetTypeCode(type))
            {

                case TypeCode.Char:

                case TypeCode.Single:

                case TypeCode.Double:

                case TypeCode.Decimal:

                    return 1;

                case TypeCode.SByte:

                case TypeCode.Int16:

                case TypeCode.Int32:

                case TypeCode.Int64:

                    return 2;

                case TypeCode.Byte:

                case TypeCode.UInt16:

                case TypeCode.UInt32:

                case TypeCode.UInt64:

                    return 3;

                default:

                    return 0;

            }

        }



        static bool IsEnumType(Type type)
        {

            return GetNonNullableType(type).IsEnum;

        }



        void CheckAndPromoteOperand(Type signatures, string opName, ref Expression expr, int errorPos)
        {

            Expression[] args = new Expression[] { expr };

            MethodBase method;

            if (FindMethod(signatures, "F", false, args, out method) != 1)

                throw ParseError(errorPos, Res.IncompatibleOperand,

                    opName, GetTypeName(args[0].Type));

            expr = args[0];

        }



        void CheckAndPromoteOperands(Type signatures, string opName, ref Expression left, ref Expression right, int errorPos)
        {

            Expression[] args = new Expression[] { left, right };

            MethodBase method;

            if (FindMethod(signatures, "F", false, args, out method) != 1)

                throw IncompatibleOperandsError(opName, left, right, errorPos);

            left = args[0];

            right = args[1];

        }



        Exception IncompatibleOperandsError(string opName, Expression left, Expression right, int pos)
        {

            return ParseError(pos, Res.IncompatibleOperands,

                opName, GetTypeName(left.Type), GetTypeName(right.Type));

        }



        MemberInfo FindPropertyOrField(Type type, string memberName, bool staticAccess)
        {

            BindingFlags flags = BindingFlags.Public | BindingFlags.DeclaredOnly |

                (staticAccess ? BindingFlags.Static : BindingFlags.Instance);

            foreach (Type t in SelfAndBaseTypes(type))
            {

                MemberInfo[] members = t.FindMembers(MemberTypes.Property | MemberTypes.Field,

                    flags, Type.FilterNameIgnoreCase, memberName);

                if (members.Length != 0) return members[0];

            }

            return null;

        }



        int FindMethod(Type type, string methodName, bool staticAccess, Expression[] args, out MethodBase method)
        {

            BindingFlags flags = BindingFlags.Public | BindingFlags.DeclaredOnly |

                (staticAccess ? BindingFlags.Static : BindingFlags.Instance);

            foreach (Type t in SelfAndBaseTypes(type))
            {

                MemberInfo[] members = t.FindMembers(MemberTypes.Method,

                    flags, Type.FilterNameIgnoreCase, methodName);

                int count = FindBestMethod(members.Cast<MethodBase>(), args, out method);

                if (count != 0) return count;

            }

            method = null;

            return 0;

        }



        int FindIndexer(Type type, Expression[] args, out MethodBase method)
        {

            foreach (Type t in SelfAndBaseTypes(type))
            {

                MemberInfo[] members = t.GetDefaultMembers();

                if (members.Length != 0)
                {

                    IEnumerable<MethodBase> methods = members.

                        OfType<PropertyInfo>().

                        Select(p => (MethodBase)p.GetGetMethod()).

                        Where(m => m != null);

                    int count = FindBestMethod(methods, args, out method);

                    if (count != 0) return count;

                }

            }

            method = null;

            return 0;

        }



        static IEnumerable<Type> SelfAndBaseTypes(Type type)
        {

            if (type.IsInterface)
            {

                List<Type> types = new List<Type>();

                AddInterface(types, type);

                return types;

            }

            return SelfAndBaseClasses(type);

        }



        static IEnumerable<Type> SelfAndBaseClasses(Type type)
        {

            while (type != null)
            {

                yield return type;

                type = type.BaseType;

            }

        }



        static void AddInterface(List<Type> types, Type type)
        {

            if (!types.Contains(type))
            {

                types.Add(type);

                foreach (Type t in type.GetInterfaces()) AddInterface(types, t);

            }

        }



        class MethodData
        {

            public MethodBase MethodBase;

            public ParameterInfo[] Parameters;

            public Expression[] Args;

        }



        int FindBestMethod(IEnumerable<MethodBase> methods, Expression[] args, out MethodBase method)
        {

            MethodData[] applicable = methods.

                Select(m => new MethodData { MethodBase = m, Parameters = m.GetParameters() }).

                Where(m => IsApplicable(m, args)).

                ToArray();

            if (applicable.Length > 1)
            {

                applicable = applicable.

                    Where(m => applicable.All(n => m == n || IsBetterThan(args, m, n))).

                    ToArray();

            }

            if (applicable.Length == 1)
            {

                MethodData md = applicable[0];

                for (int i = 0; i < args.Length; i++) args[i] = md.Args[i];

                method = md.MethodBase;

            }

            else
            {

                method = null;

            }

            return applicable.Length;

        }



        bool IsApplicable(MethodData method, Expression[] args)
        {

            if (method.Parameters.Length != args.Length) return false;

            Expression[] promotedArgs = new Expression[args.Length];

            for (int i = 0; i < args.Length; i++)
            {

                ParameterInfo pi = method.Parameters[i];

                if (pi.IsOut) return false;

                Expression promoted = PromoteExpression(args[i], pi.ParameterType, false);

                if (promoted == null) return false;

                promotedArgs[i] = promoted;

            }

            method.Args = promotedArgs;

            return true;

        }



        Expression PromoteExpression(Expression expr, Type type, bool exact)
        {

            if (expr.Type == type) return expr;

            if (expr is ConstantExpression)
            {

                ConstantExpression ce = (ConstantExpression)expr;

                if (ce == nullLiteral)
                {

                    if (!type.IsValueType || IsNullableType(type))

                        return Expression.Constant(null, type);

                }

                else
                {

                    string text;

                    if (literals.TryGetValue(ce, out text))
                    {

                        Type target = GetNonNullableType(type);

                        Object value = null;

                        switch (Type.GetTypeCode(ce.Type))
                        {

                            case TypeCode.Int32:

                            case TypeCode.UInt32:

                            case TypeCode.Int64:

                            case TypeCode.UInt64:

                                value = ParseNumber(text, target);

                                break;

                            case TypeCode.Double:

                                if (target == typeof(decimal)) value = ParseNumber(text, target);

                                break;

                            case TypeCode.String:

                                value = ParseEnum(text, target);

                                break;

                        }

                        if (value != null)

                            return Expression.Constant(value, type);

                    }

                }

            }

            if (IsCompatibleWith(expr.Type, type))
            {

                if (type.IsValueType || exact) return Expression.Convert(expr, type);

                return expr;

            }

            return null;

        }



        static object ParseNumber(string text, Type type)
        {

            switch (Type.GetTypeCode(GetNonNullableType(type)))
            {

                case TypeCode.SByte:

                    sbyte sb;

                    if (sbyte.TryParse(text, out sb)) return sb;

                    break;

                case TypeCode.Byte:

                    byte b;

                    if (byte.TryParse(text, out b)) return b;

                    break;

                case TypeCode.Int16:

                    short s;

                    if (short.TryParse(text, out s)) return s;

                    break;

                case TypeCode.UInt16:

                    ushort us;

                    if (ushort.TryParse(text, out us)) return us;

                    break;

                case TypeCode.Int32:

                    int i;

                    if (int.TryParse(text, out i)) return i;

                    break;

                case TypeCode.UInt32:

                    uint ui;

                    if (uint.TryParse(text, out ui)) return ui;

                    break;

                case TypeCode.Int64:

                    long l;

                    if (long.TryParse(text, out l)) return l;

                    break;

                case TypeCode.UInt64:

                    ulong ul;

                    if (ulong.TryParse(text, out ul)) return ul;

                    break;

                case TypeCode.Single:

                    float f;

                    if (float.TryParse(text, out f)) return f;

                    break;

                case TypeCode.Double:

                    double d;

                    if (double.TryParse(text, out d)) return d;

                    break;

                case TypeCode.Decimal:

                    decimal e;

                    if (decimal.TryParse(text, out e)) return e;

                    break;

            }

            return null;

        }



        static object ParseEnum(string name, Type type)
        {

            if (type.IsEnum)
            {

                MemberInfo[] memberInfos = type.FindMembers(MemberTypes.Field,

                    BindingFlags.Public | BindingFlags.DeclaredOnly | BindingFlags.Static,

                    Type.FilterNameIgnoreCase, name);

                if (memberInfos.Length != 0) return ((FieldInfo)memberInfos[0]).GetValue(null);

            }

            return null;

        }



        static bool IsCompatibleWith(Type source, Type target)
        {

            if (source == target) return true;

            if (!target.IsValueType) return target.IsAssignableFrom(source);

            Type st = GetNonNullableType(source);

            Type tt = GetNonNullableType(target);

            if (st != source && tt == target) return false;

            TypeCode sc = st.IsEnum ? TypeCode.Object : Type.GetTypeCode(st);

            TypeCode tc = tt.IsEnum ? TypeCode.Object : Type.GetTypeCode(tt);

            switch (sc)
            {

                case TypeCode.SByte:

                    switch (tc)
                    {

                        case TypeCode.SByte:

                        case TypeCode.Int16:

                        case TypeCode.Int32:

                        case TypeCode.Int64:

                        case TypeCode.Single:

                        case TypeCode.Double:

                        case TypeCode.Decimal:

                            return true;

                    }

                    break;

                case TypeCode.Byte:

                    switch (tc)
                    {

                        case TypeCode.Byte:

                        case TypeCode.Int16:

                        case TypeCode.UInt16:

                        case TypeCode.Int32:

                        case TypeCode.UInt32:

                        case TypeCode.Int64:

                        case TypeCode.UInt64:

                        case TypeCode.Single:

                        case TypeCode.Double:

                        case TypeCode.Decimal:

                            return true;

                    }

                    break;

                case TypeCode.Int16:

                    switch (tc)
                    {

                        case TypeCode.Int16:

                        case TypeCode.Int32:

                        case TypeCode.Int64:

                        case TypeCode.Single:

                        case TypeCode.Double:

                        case TypeCode.Decimal:

                            return true;

                    }

                    break;

                case TypeCode.UInt16:

                    switch (tc)
                    {

                        case TypeCode.UInt16:

                        case TypeCode.Int32:

                        case TypeCode.UInt32:

                        case TypeCode.Int64:

                        case TypeCode.UInt64:

                        case TypeCode.Single:

                        case TypeCode.Double:

                        case TypeCode.Decimal:

                            return true;

                    }

                    break;

                case TypeCode.Int32:

                    switch (tc)
                    {

                        case TypeCode.Int32:

                        case TypeCode.Int64:

                        case TypeCode.Single:

                        case TypeCode.Double:

                        case TypeCode.Decimal:

                            return true;

                    }

                    break;

                case TypeCode.UInt32:

                    switch (tc)
                    {

                        case TypeCode.UInt32:

                        case TypeCode.Int64:

                        case TypeCode.UInt64:

                        case TypeCode.Single:

                        case TypeCode.Double:

                        case TypeCode.Decimal:

                            return true;

                    }

                    break;

                case TypeCode.Int64:

                    switch (tc)
                    {

                        case TypeCode.Int64:

                        case TypeCode.Single:

                        case TypeCode.Double:

                        case TypeCode.Decimal:

                            return true;

                    }

                    break;

                case TypeCode.UInt64:

                    switch (tc)
                    {

                        case TypeCode.UInt64:

                        case TypeCode.Single:

                        case TypeCode.Double:

                        case TypeCode.Decimal:

                            return true;

                    }

                    break;

                case TypeCode.Single:

                    switch (tc)
                    {

                        case TypeCode.Single:

                        case TypeCode.Double:

                            return true;

                    }

                    break;

                default:

                    if (st == tt) return true;

                    break;

            }

            return false;

        }



        static bool IsBetterThan(Expression[] args, MethodData m1, MethodData m2)
        {

            bool better = false;

            for (int i = 0; i < args.Length; i++)
            {

                int c = CompareConversions(args[i].Type,

                    m1.Parameters[i].ParameterType,

                    m2.Parameters[i].ParameterType);

                if (c < 0) return false;

                if (c > 0) better = true;

            }

            return better;

        }



        // Return 1 if s -> t1 is a better conversion than s -> t2

        // Return -1 if s -> t2 is a better conversion than s -> t1

        // Return 0 if neither conversion is better

        static int CompareConversions(Type s, Type t1, Type t2)
        {

            if (t1 == t2) return 0;

            if (s == t1) return 1;

            if (s == t2) return -1;

            bool t1t2 = IsCompatibleWith(t1, t2);

            bool t2t1 = IsCompatibleWith(t2, t1);

            if (t1t2 && !t2t1) return 1;

            if (t2t1 && !t1t2) return -1;

            if (IsSignedIntegralType(t1) && IsUnsignedIntegralType(t2)) return 1;

            if (IsSignedIntegralType(t2) && IsUnsignedIntegralType(t1)) return -1;

            return 0;

        }



        Expression GenerateEqual(Expression left, Expression right)
        {

            return Expression.Equal(left, right);

        }



        Expression GenerateNotEqual(Expression left, Expression right)
        {

            return Expression.NotEqual(left, right);

        }



        Expression GenerateGreaterThan(Expression left, Expression right)
        {

            if (left.Type == typeof(string))
            {

                return Expression.GreaterThan(

                    GenerateStaticMethodCall("Compare", left, right),

                    Expression.Constant(0)

                );

            }

            return Expression.GreaterThan(left, right);

        }



        Expression GenerateGreaterThanEqual(Expression left, Expression right)
        {

            if (left.Type == typeof(string))
            {

                return Expression.GreaterThanOrEqual(

                    GenerateStaticMethodCall("Compare", left, right),

                    Expression.Constant(0)

                );

            }

            return Expression.GreaterThanOrEqual(left, right);

        }



        Expression GenerateLessThan(Expression left, Expression right)
        {

            if (left.Type == typeof(string))
            {

                return Expression.LessThan(

                    GenerateStaticMethodCall("Compare", left, right),

                    Expression.Constant(0)

                );

            }

            return Expression.LessThan(left, right);

        }



        Expression GenerateLessThanEqual(Expression left, Expression right)
        {

            if (left.Type == typeof(string))
            {

                return Expression.LessThanOrEqual(

                    GenerateStaticMethodCall("Compare", left, right),

                    Expression.Constant(0)

                );

            }

            return Expression.LessThanOrEqual(left, right);

        }



        Expression GenerateAdd(Expression left, Expression right)
        {

            if (left.Type == typeof(string) && right.Type == typeof(string))
            {

                return GenerateStaticMethodCall("Concat", left, right);

            }

            return Expression.Add(left, right);

        }



        Expression GenerateSubtract(Expression left, Expression right)
        {

            return Expression.Subtract(left, right);

        }



        Expression GenerateStringConcat(Expression left, Expression right)
        {

            return Expression.Call(

                null,

                typeof(string).GetMethod("Concat", new[] { typeof(object), typeof(object) }),

                new[] { left, right });

        }



        MethodInfo GetStaticMethod(string methodName, Expression left, Expression right)
        {

            return left.Type.GetMethod(methodName, new[] { left.Type, right.Type });

        }



        Expression GenerateStaticMethodCall(string methodName, Expression left, Expression right)
        {

            return Expression.Call(null, GetStaticMethod(methodName, left, right), new[] { left, right });

        }



        void SetTextPos(int pos)
        {

            textPos = pos;

            ch = textPos < textLen ? text[textPos] : '\0';

        }



        void NextChar()
        {

            if (textPos < textLen) textPos++;

            ch = textPos < textLen ? text[textPos] : '\0';

        }



        void NextToken()
        {

            while (Char.IsWhiteSpace(ch)) NextChar();

            TokenId t;

            int tokenPos = textPos;

            switch (ch)
            {

                case '!':

                    NextChar();

                    if (ch == '=')
                    {

                        NextChar();

                        t = TokenId.ExclamationEqual;

                    }

                    else
                    {

                        t = TokenId.Exclamation;

                    }

                    break;

                case '%':

                    NextChar();

                    t = TokenId.Percent;

                    break;

                case '&':

                    NextChar();

                    if (ch == '&')
                    {

                        NextChar();

                        t = TokenId.DoubleAmphersand;

                    }

                    else
                    {

                        t = TokenId.Amphersand;

                    }

                    break;

                case '(':

                    NextChar();

                    t = TokenId.OpenParen;

                    break;

                case ')':

                    NextChar();

                    t = TokenId.CloseParen;

                    break;

                case '*':

                    NextChar();

                    t = TokenId.Asterisk;

                    break;

                case '+':

                    NextChar();

                    t = TokenId.Plus;

                    break;

                case ',':

                    NextChar();

                    t = TokenId.Comma;

                    break;

                case '-':

                    NextChar();

                    t = TokenId.Minus;

                    break;

                case '.':

                    NextChar();

                    t = TokenId.Dot;

                    break;

                case '/':

                    NextChar();

                    t = TokenId.Slash;

                    break;

                case ':':

                    NextChar();

                    t = TokenId.Colon;

                    break;

                case '<':

                    NextChar();

                    if (ch == '=')
                    {

                        NextChar();

                        t = TokenId.LessThanEqual;

                    }

                    else if (ch == '>')
                    {

                        NextChar();

                        t = TokenId.LessGreater;

                    }

                    else
                    {

                        t = TokenId.LessThan;

                    }

                    break;

                case '=':

                    NextChar();

                    if (ch == '=')
                    {

                        NextChar();

                        t = TokenId.DoubleEqual;

                    }

                    else
                    {

                        t = TokenId.Equal;

                    }

                    break;

                case '>':

                    NextChar();

                    if (ch == '=')
                    {

                        NextChar();

                        t = TokenId.GreaterThanEqual;

                    }

                    else
                    {

                        t = TokenId.GreaterThan;

                    }

                    break;

                case '?':

                    NextChar();

                    t = TokenId.Question;

                    break;

                case '[':

                    NextChar();

                    t = TokenId.OpenBracket;

                    break;

                case ']':

                    NextChar();

                    t = TokenId.CloseBracket;

                    break;

                case '|':

                    NextChar();

                    if (ch == '|')
                    {

                        NextChar();

                        t = TokenId.DoubleBar;

                    }

                    else
                    {

                        t = TokenId.Bar;

                    }

                    break;

                case '"':

                case '\'':

                    char quote = ch;

                    do
                    {

                        NextChar();

                        while (textPos < textLen && ch != quote) NextChar();

                        if (textPos == textLen)

                            throw ParseError(textPos, Res.UnterminatedStringLiteral);

                        NextChar();

                    } while (ch == quote);

                    t = TokenId.StringLiteral;

                    break;

                default:

                    if (Char.IsLetter(ch) || ch == '@' || ch == '_')
                    {

                        do
                        {

                            NextChar();

                        } while (Char.IsLetterOrDigit(ch) || ch == '_');

                        t = TokenId.Identifier;

                        break;

                    }

                    if (Char.IsDigit(ch))
                    {

                        t = TokenId.IntegerLiteral;

                        do
                        {

                            NextChar();

                        } while (Char.IsDigit(ch));

                        if (ch == '.')
                        {

                            t = TokenId.RealLiteral;

                            NextChar();

                            ValidateDigit();

                            do
                            {

                                NextChar();

                            } while (Char.IsDigit(ch));

                        }

                        if (ch == 'E' || ch == 'e')
                        {

                            t = TokenId.RealLiteral;

                            NextChar();

                            if (ch == '+' || ch == '-') NextChar();

                            ValidateDigit();

                            do
                            {

                                NextChar();

                            } while (Char.IsDigit(ch));

                        }

                        if (ch == 'F' || ch == 'f') NextChar();

                        break;

                    }

                    if (textPos == textLen)
                    {

                        t = TokenId.End;

                        break;

                    }

                    throw ParseError(textPos, Res.InvalidCharacter, ch);

            }

            token.id = t;

            token.text = text.Substring(tokenPos, textPos - tokenPos);

            token.pos = tokenPos;

        }



        bool TokenIdentifierIs(string id)
        {

            return token.id == TokenId.Identifier && String.Equals(id, token.text, StringComparison.OrdinalIgnoreCase);

        }



        string GetIdentifier()
        {

            ValidateToken(TokenId.Identifier, Res.IdentifierExpected);

            string id = token.text;

            if (id.Length > 1 && id[0] == '@') id = id.Substring(1);

            return id;

        }



        void ValidateDigit()
        {

            if (!Char.IsDigit(ch)) throw ParseError(textPos, Res.DigitExpected);

        }



        void ValidateToken(TokenId t, string errorMessage)
        {

            if (token.id != t) throw ParseError(errorMessage);

        }



        void ValidateToken(TokenId t)
        {

            if (token.id != t) throw ParseError(Res.SyntaxError);

        }



        Exception ParseError(string format, params object[] args)
        {

            return ParseError(token.pos, format, args);

        }



        Exception ParseError(int pos, string format, params object[] args)
        {

            return new ParseException(string.Format(System.Globalization.CultureInfo.CurrentCulture, format, args), pos);

        }



        static Dictionary<string, object> CreateKeywords()
        {

            Dictionary<string, object> d = new Dictionary<string, object>(StringComparer.OrdinalIgnoreCase);

            d.Add("true", trueLiteral);

            d.Add("false", falseLiteral);

            d.Add("null", nullLiteral);

            d.Add(keywordIt, keywordIt);

            d.Add(keywordIif, keywordIif);

            d.Add(keywordNew, keywordNew);

            foreach (Type type in predefinedTypes) d.Add(type.Name, type);

            return d;

        }

    }



    static class Res
    {

        public const string DuplicateIdentifier = "The identifier '{0}' was defined more than once";

        public const string ExpressionTypeMismatch = "Expression of type '{0}' expected";

        public const string ExpressionExpected = "Expression expected";

        public const string InvalidCharacterLiteral = "Character literal must contain exactly one character";

        public const string InvalidIntegerLiteral = "Invalid integer literal '{0}'";

        public const string InvalidRealLiteral = "Invalid real literal '{0}'";

        public const string UnknownIdentifier = "Unknown identifier '{0}'";

        public const string NoItInScope = "No 'it' is in scope";

        public const string IifRequiresThreeArgs = "The 'iif' function requires three arguments";

        public const string FirstExprMustBeBool = "The first expression must be of type 'Boolean'";

        public const string BothTypesConvertToOther = "Both of the types '{0}' and '{1}' convert to the other";

        public const string NeitherTypeConvertsToOther = "Neither of the types '{0}' and '{1}' converts to the other";

        public const string MissingAsClause = "Expression is missing an 'as' clause";

        public const string ArgsIncompatibleWithLambda = "Argument list incompatible with lambda expression";

        public const string TypeHasNoNullableForm = "Type '{0}' has no nullable form";

        public const string NoMatchingConstructor = "No matching constructor in type '{0}'";

        public const string AmbiguousConstructorInvocation = "Ambiguous invocation of '{0}' constructor";

        public const string CannotConvertValue = "A value of type '{0}' cannot be converted to type '{1}'";

        public const string NoApplicableMethod = "No applicable method '{0}' exists in type '{1}'";

        public const string MethodsAreInaccessible = "Methods on type '{0}' are not accessible";

        public const string MethodIsVoid = "Method '{0}' in type '{1}' does not return a value";

        public const string AmbiguousMethodInvocation = "Ambiguous invocation of method '{0}' in type '{1}'";

        public const string UnknownPropertyOrField = "No property or field '{0}' exists in type '{1}'";

        public const string NoApplicableAggregate = "No applicable aggregate method '{0}' exists";

        public const string CannotIndexMultiDimArray = "Indexing of multi-dimensional arrays is not supported";

        public const string InvalidIndex = "Array index must be an integer expression";

        public const string NoApplicableIndexer = "No applicable indexer exists in type '{0}'";

        public const string AmbiguousIndexerInvocation = "Ambiguous invocation of indexer in type '{0}'";

        public const string IncompatibleOperand = "Operator '{0}' incompatible with operand type '{1}'";

        public const string IncompatibleOperands = "Operator '{0}' incompatible with operand types '{1}' and '{2}'";

        public const string UnterminatedStringLiteral = "Unterminated string literal";

        public const string InvalidCharacter = "Syntax error '{0}'";

        public const string DigitExpected = "Digit expected";

        public const string SyntaxError = "Syntax error";

        public const string TokenExpected = "{0} expected";

        public const string ParseExceptionFormat = "{0} (at index {1})";

        public const string ColonExpected = "':' expected";

        public const string OpenParenExpected = "'(' expected";

        public const string CloseParenOrOperatorExpected = "')' or operator expected";

        public const string CloseParenOrCommaExpected = "')' or ',' expected";

        public const string DotOrOpenParenExpected = "'.' or '(' expected";

        public const string OpenBracketExpected = "'[' expected";

        public const string CloseBracketOrCommaExpected = "']' or ',' expected";

        public const string IdentifierExpected = "Identifier expected";

    }

}



